# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 4.full_alignment.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2021/11/29 15:54
------------------------------------------
    不带重复数字的全排列问题
"""
from copy import deepcopy

res = []


def permute(nums: list):
    """
        permute，重排序
        输入一组不重复的数，返回它们的全排列
    """

    # 记录路径
    track = []
    backtrack(nums, track)

    return res


def backtrack(nums: list, track: list):
    """
        路径：记录在track中
        选择列表：nums中不存在于track中的那些元素
        结束条件：nums中的元素全部都在track中

        注意：
            这里的 res的元素是列表，在Python中列表嵌套列表时，内层列表是引用，而不是实际的值。
            所以，这里要注意深、浅层拷贝的问题
    """
    if len(track) == len(nums):
        res.append(deepcopy(track))
        return

    for i in nums:
        if i in track:
            continue

        # 做选择
        track.append(i)

        # 进入下一层决策树
        backtrack(nums, track)
        # 移除最后添加的元素
        track.pop()


def python_copy_demo():
    """
        演示函数 backtrack中涉及到的深浅层拷贝问题
    """
    lis = []
    a = [1, 2, 3]
    b = a
    c = deepcopy(a)

    for i in [a, b, c]:
        lis.append(i)

    print(f"lis: {lis}")

    a.pop()
    b.insert(0, 'b_insert')
    c.insert(0, 'c_insert')
    print(f"lis: {lis}")


if __name__ == '__main__':
    test_l = [1, 2, 3]
    data = permute(test_l)

    print(data)
    print("===============\n python_copy_demo")
    python_copy_demo()
